(1) Field of the Invention
The present invention generally relates to a signal processing system and more particularly, but not by way of limitation, to a system and method of use for non-parametric circular autocorrelation for signal processing.
(2) Description of the Prior Art
In signal processing studies four important functions may be used to describe or model a finite stationary signal x(t),t≧0 whether it be periodic, transient or random, or based on a single source or multiple sources (an ensemble) of input data. These functions are the mean square value, probability density function (PDF), autocorrelation function (ACF) and power spectral density (PSD).
Autocorrelation is generally the cross-correlation of a signal with itself. It describes the dependence of a signal's value at one point with the value of the same signal at another time. The measure is designed to detect repeating patterns or trends in noise-corrupted nonlinear time series distributions (e.g., periodic, quasi-periodic, parabolic, etc.) and identify frequencies. The ACF is one measure to determine whether the time waveform is random noise. The ACF is a basic building block of time series analysis. It has applications to diverse fields including signal processing, oceanography, astrophysics, finance & economics, quality control, physiology, epidemiology, demography, statistics and other applied areas of science and engineering.
The ACF is generally defined as:
                                          R            ⁡                          (              τ              )                                =                                    E              ⁡                              [                                                      (                                                                  X                        t                                            -                      μ                                        )                                    ⁢                                      (                                                                  X                                                  t                          +                          τ                                                                    -                      μ                                        )                                                  ]                                                    σ              2                                      ,                              -            1                    ≤                      R            ⁡                          (              τ              )                                ≤                      +            1                                              (        1        )            where E is the expected value operator, t is the discrete or continuous variable time, τ is the time lag, μ is the mean, σ2 is the variance. σ2 and μ are time independent.
Various modifications are made to this formula depending upon the measurements (discrete or continuous) and other assumptions relating to stationarity, ergodicity, etc. For instance, in naval sonar signal processing with positive time t the definition of the ACF used for analysis of stationary random signals x(t),t≧0, takes the time average limiting form,
                                          R            xx                    ⁡                      (            τ            )                          =                              lim                          T              →              ∞                                ⁢                                    1              T                        ⁢                                          ∫                0                T                            ⁢                                                X                  ⁡                                      (                    t                    )                                                  ⁢                                  x                  ⁡                                      (                                          t                      +                      τ                                        )                                                  ⁢                                                                  ⁢                                  ⅆ                  t                                                                                        (                  1          ⁢          a                )            when the process is assumed to be ergodic-defined in one way as a positive recurrent aperiodic state of stochastic systems, or tending in probability to a limiting form that is independent of the initial conditions—a condition usually encountered in sonar signal studies.
The autocorrelation function (discrete or continuous time models) has certain basic properties. The autocorrelation function is a symmetric around 0 (or an even function for continuous case), R(τ)=R(−τ). The autocorrelation function will have its largest value at the origin, when time lag τ=0; R(0)≧R(τ). The autocorrelation of a periodic function will also be periodic with the same frequency. Other properties, well known to those skilled in the art, also exist. In addition, specific types of noise such as white and colored noise, and functional forms have documented characteristics.
With respect to circular correlation, the normalized circular autocorrelation function for a discrete time process can be described as arising from the classical Pearson linear correlation function for a data set consisting of n bivariate pairs x1y1, x2y2, . . . xnyn. The linear correlation r for samples of size n can be expressed as a definition:
                                          r                          x              ,              y                                =                                                    1                                  n                  -                  1                                            ⁢                                                ∑                                      i                    =                    1                                    n                                ⁢                                                      (                                                                  x                        i                                            -                                              x                        _                                                              )                                    ⁢                                      (                                                                  y                        i                                            -                                              y                        _                                                              )                                                                                                                        (                                                            1                                              n                        -                        1                                                              ⁢                                                                  ∑                                                  i                          =                          1                                                n                                            ⁢                                                                        (                                                                                    x                              i                                                        -                                                          x                              _                                                                                )                                                2                                                                              )                                ⁢                                  (                                                            1                                              n                        -                        1                                                              ⁢                                                                  ∑                                                  i                          =                          1                                                n                                            ⁢                                                                        (                                                                                    y                              i                                                        -                                                          y                              _                                                                                )                                                2                                                                              )                                                                    ,                                  ⁢                              -            1                    ≤                      r                          x              ,              y                                ≤                      +            1                                              (        2        )            
This definition of can be simplified to a well-known computing formula:
                              r                      x            ,            y                          =                                                            ∑                                  i                  =                  1                                n                            ⁢                                                x                  i                                ⁢                                  y                  i                                                      -                                                            ∑                                      i                    =                    1                                    n                                ⁢                                                      x                    i                                    ⁢                                                            ∑                                              i                        =                        1                                            n                                        ⁢                                          y                      i                                                                                  n                                                                          (                                                                            ∑                                              i                        =                        1                                            n                                        ⁢                                          x                      i                      2                                                        -                                                                                    (                                                                              ∑                                                          i                              =                              1                                                        n                                                    ⁢                                                      x                            i                                                                          )                                            2                                        n                                                  )                            ⁢                              (                                                                            ∑                                              i                        =                        1                                            n                                        ⁢                                          y                      i                      2                                                        -                                                                                    (                                                                              ∑                                                          i                              =                              1                                                        n                                                    ⁢                                                      y                            i                                                                          )                                            2                                        n                                                  )                                                                        (        3        )            where x and y are arithmetic means.
The circular normalized ±1 correlation coefficient is derived from index rx,y by a structured process that systematically recycles the input observations x1y1, x2y2, . . . xnyn in circular fashion of varying lag-length h. That is, each vector of lagged data contains the same measurements structured in a circular pattern. For the first lag set
            ∑              i        =        1            n        ⁢          x      i        =            ∑              i        =        1            n        ⁢          y      i      and
                    ∑                  i          =          1                n            ⁢              x        i        2              =                  ∑                  i          =          1                n            ⁢              y        i        2              ,substitute xi-1 for yi and, for the last pair, put x1 for xn+1 in formula (3) above to render the 1-lag circular correlation index,
                                          R                          x              ,                              x                +                1                                              =                                                                      ∑                                      i                    =                    1                                                        n                    -                    1                                                  ⁢                                                      x                    i                                    ⁢                                      x                                          i                      +                      1                                                                                  +                                                x                  n                                ⁢                                  x                  1                                            -                                                                    (                                                                  ∑                                                  i                          =                          1                                                n                                            ⁢                                              x                        i                                                              )                                    2                                n                                                                                      ∑                                      i                    =                    1                                    n                                ⁢                                  x                  i                  2                                            -                                                                    (                                                                  ∑                                                  i                          =                          1                                                n                                            ⁢                                              x                        i                                                              )                                    2                                n                                                    ,                              -            1                    ≤          R          ≤                      +            1                                              (        4        )            
Wald, A. and J. Wolfowitz, An exact test for randomness in the non-Parametric case based on serial correlation, Annals of Mathematical Statistics Vol. 14, No. 4, pages 378-388, 1943, (hereinafter “Wald and Wolfowitz”) provides a non-parametric permutations method such that if n is sufficiently large the 1-lag correlation of formula (4) above can be tested to determine if the distribution is random based on the statistic,
            ∑              i        =        1                    n        -        1              ⁢                  x        i            ⁢              x                  i          +          1                      +            x      n        ⁢                  x        1            .      Some researchers suggest that n>75 is required for the theoretical assumptions of the test to be valid (Giles, S., Random-noise filter based on circular correlation, Southeastern Symposium Systems Theory, 2009. http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=04806850; hereinafter “Giles”) while others suggest n≧50 (Kay, S. M. and L. Pakula, Detection performance of the circular correlation coefficient receiver. IEEE Transactions on Acoustics, Speech, and Signal Processing, Vol. ASSP-34, no. 3, June 1986, pages 399-404. Hereinafter “Kay et al.”) but many standard textbooks place a lower bound of 25. In accordance with the present disclosure, 25 may be selected as the minimum although truly random samples even as small as 15 can be detected for pure noise. This is a novel and efficient idea. Non-circular autocorrelation methods, which typically assume a Gaussian distribution, often analyze many more lags before a decision of “signal” or “noise” is made.
In a similar fashion, to obtain the autocorrelation for an arbitrary lag of length h, the circular index can be calculated by the derived formula:
                                          R                          x              ,                              x                +                h                                              =                                                                      ∑                                      i                    =                    1                                                        n                    -                    h                                                  ⁢                                                      x                    i                                    ⁢                                      x                                          i                      +                      h                                                                                  +                                                ∑                                      i                    =                    1                                    h                                ⁢                                                      x                                          i                      +                      n                      -                      h                                                        ⁢                                      x                    i                                                              -                                                                    (                                                                  ∑                                                  i                          =                          1                                                n                                            ⁢                                              x                        i                                                              )                                    2                                n                                                                                      ∑                                      i                    =                    1                                    n                                ⁢                                  x                  i                  2                                            -                                                                    (                                                                  ∑                                                  i                          =                          1                                                n                                            ⁢                                              x                        i                                                              )                                    2                                n                                                    ,                                  ⁢                                            -              1                        ≤                          R                              x                ,                                  x                  +                  h                                                      ≤                          +              1                                ;                      0            ≤            h            ≤                          n              -              1.                                                          (        5        )            Application of the non-circular form of equation (5) omits the second term of
            ∑              i        =        1                    n        -        h              ⁢                  ⁢                  x        i            ⁢              x                  i          +          h                      +            ∑              i        =        1            h        ⁢                  ⁢                  x                  i          +          n          -          h                    ⁢                        x          i                .            
In some aspects, the same identical n data points are used in a wrap-around circular fashion for any lag in the computation of the ACF. The standard discrete non-circular correlation index removes one observation with each lag calculation, a serious drawback for small samples, a condition for which the present disclosure models accurately and efficiently.
Wald and Wolfowitz generally describe the properties of Rx,x+h in the context of non-parametric (or distribution free) methods. To summarize the large sample non-parametric approach of Wald and Wolfowitz at page 378 provide:                a sequence of variates x1, . . . , xN is said to be a random series, or to satisfy the condition of randomness, if x1, . . . , xN are independently distributed; i.e., if the joint cumulative distribution function (c.d.f.) of x1, . . . , xN is given by the product F(x1) . . . F(xN) where F(x) may be any c.d.f.        
This method has been adapted for application in signal processing studies of random signals to determine if the distribution is random and to document other properties of the signal structure such as periodicities or other trends. The underlying distribution function may be continuous or discrete.
Further, a number of prior art references address various aspects of signal processing methodologies/techniques. For example, U.S. Pat. No. 7,369,961, to Castelli et al., relates to clustering structures of time sequences. Generally, the Castelli et al. patent discloses a system and method to discover potential periodicities of time series by examining power spectral density (PSD) and circular autocorrelation functions (ACFs). Their ACF formula is designed to “estimate dominant periods of a time series.” (Col. 4, lines 55-56). The present disclosure, however, uses an entirely different circular autocorrelation function and addresses a different purpose.
Other prior art references include, for example, U.S. Pat. Nos. 5,966,414 and 6,597,634, to O'Brien et al. (of the present disclosure). These patents generally relate to methods for distinguishing signal from noise in time-series data. However, these patents do not teach or suggest the present disclosure. For example, these patents can be distinguished in the dimensionality analyzed, the ensemble of statistical and probability methods for data analysis. Neither patent uses a circular autocorrelation method for signal/noise determination.
In view of the above, there is a need for an improved system on non-parametric circular autocorrelation for signal processing and method of use, such as is described in the present disclosure.